各依次输入递增有序若干个不超过100的整数，分别建立两个递增有序单链表，分别表示集合A和集合B。设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并存放于A链表中。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。然后输出求的差集的单链表。测试数据保证结果链表至少存在一个元素。

输入格式:

首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据先在第一行输入数据个数n及n个依次递增有序的不超过100的整数，再在第二行输入数据个数m及m个依次递增有序的不超过100的整数。

输出格式:

对于每组测试，输出A与B的差集的单链表，每两个数据之间留一个空格。

输入样例:

1
2
3
4
5
2
11 10 14 23 25 26 31 34 42 51 65 90
10 10 41 42 46 51 58 59 60 68 97
5 1 2 3 4 5
3 3 4 5

输出样例:

1
2
14 23 25 26 31 34 65 90
1 2

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<stdio.h>
#include<malloc.h>
using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;

void CreatelistR(LNode *&head,int arr[],int n);//尾插法创建带头结点的单向链表
void ShowList(LNode *head);

//求A与B的交叉集(仅在A中出现而不在B中出现)，并将结果保存到链表A
void Difference(LNode *A,LNode *B);//时间复杂度O（m+n)

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        int tmp;//临时变量

        LNode *head = nullptr;
        int arr[100] = {0};
        int n1;
        scanf("%d",&n1);
        for(int i = 0; i < n1; i++)
        {
            scanf("%d",&tmp);
            arr[i] = tmp;
        }

        CreatelistR(head,arr,n1);

        LNode *head_2 = nullptr;
        int arr_2[100] = {0};
        int n2;
        scanf("%d",&n2);
        for(int i = 0; i < n2; i++)
        {
            scanf("%d",&tmp);
            arr_2[i] = tmp;
        }

        CreatelistR(head_2,arr_2,n2);

        Difference(head,head_2);
        ShowList(head);
    }
    return 0;
}

void CreatelistR(LNode *&head,int arr[],int n)//尾插法
{
    if(arr == nullptr || n < 0)
        return;
    head = (LNode *)malloc(sizeof(LNode));
    head->next = nullptr;

    LNode *temp = head;
    for(int i=0; i<n; i++)
    {
        LNode *node = (LNode *)malloc(sizeof(LNode));
        node->data = arr[i];
        node->next = nullptr;

        temp->next = node;
        temp = temp->next;
    }
}

void ShowList(LNode *head)
{
    if(head == nullptr)
        return;
    while(head->next != nullptr)
    {
        if(head->next->next == nullptr)
            printf("%d",head->next->data);
        else
            printf("%d ",head->next->data);
        head = head->next;
    }
    printf("\n");
}

//求A与B的交叉集(仅在A中出现而不在B中出现)，并将结果保存到链表A
void Difference(LNode *A,LNode *B)//时间复杂度O（m+n)
{
    if(A == nullptr || B == nullptr)
        return ;
    LNode *p = A->next,*q = B->next;
    LNode *r = A;//记录前置结点

    while(p != nullptr && q != nullptr)
    {
        if(p->data < q->data)
        {
            r = p;
            p = p->next;
        }
        else if(p->data > q->data)
        {
            q = q->next;
        }
        else
        {
            LNode *s = p;
            r->next = p->next;//记得重新指向

            p = p->next;
            free(s);
        }
    }
}